package org.xiaojinlong.algo;

/**
 * The <tt>Insertion</tt> class provides static methods for sorting an
 * array using an optimized version of insertion sort (with half exchanges and a sentinel).
 * @author Jin Long
 * 2015/8/23
 */
public class Insertion {
    private Insertion() { }

    /**
     * Rearranges the array in ascending order, using the natural order.
     * @param a the array to be sorted
     */
    public static void sort(Comparable[] a) {
        int N = a.length;

        if (N == 1) {
            return;
        }

        // put smallest element in position to serve as sentinel
        for (int i = N-1; i > 0; i--) {
            if (less(a[i], a[i - 1])) {
                exch(a, i, i - 1);
            }
        }

        if (N < 2) {
            return; // only 2 elements
        }

        // insertion sort with half-exchanges
        for (int i = 2; i < N; i++) {
            Comparable key = a[i];
            int j = i;
            while (less(key, a[j-1])) {
                a[j] = a[j-1];
                j--;
            }
            a[j] = key;
        }

        assert isSorted(a);
    }

    /************************************************************
     * Helper sorting functions.
     ***********************************************************/

    // is v < w ?
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    // exchange a[i] and a[j]
    private static void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    /************************************************************
     * Check if array is sorted - useful for debugging.
     ************************************************************/
    private static boolean isSorted(Comparable[] a) {
        if (a.length == 1) {
            return true;
        }

        for (int i = 1; i < a.length; i++) {
            if (less(a[i], a[i-1])) {
                return false;
            }
        }

        return true;
    }


}
